package l07_dynamic_planning;

/**
 * 人民币组成固定金额的张数最小
 *
 * @author wangxiyue@cyou-inc.com
 * @date 2019-08-15
 * @since 1.0.0
 */
public class Money {

    public static void main(String[] args) {
        combine(101);
    }

    static int[] moneyType = {1, 2, 5, 10, 20, 50, 100};


    private static int combine(int money) {

        // 表示当前金额的最小张数
        int c[] = new int[money + 1];

        for (int i = 0; i < money; i++) {
            int min = Integer.MAX_VALUE - 1;
            for (int j = 0; j < moneyType.length; j++) {
                int m = moneyType[j];
                if (i == m) {
                    min = 1;
                    break;
                } else if (i > m) {
                    min = Math.min(min + 1, c[i - m] + 1);
                } else {
                    break;
                }
            }
            System.out.printf("%d--%d\n", i, min);
            c[i] = min;
        }
        return c[money];
    }


}

